#include<iostream>
#include<stdio.h>
#include<malloc.h>
#define INF 32767
#define MAXV 100
using namespace std;
typedef char InfoType;

typedef struct
{
	int no;
	InfoType info;
}VertexType;
typedef struct
{
	int edges[MAXV][MAXV];
	int n,e;
	VertexType vexs[MAXV];
}MatGraph;

typedef struct ANode
{
	int adjvex;
	struct ANode *nextarc;
	int weight;
}ArcNode;
typedef struct Vnode
{
	InfoType info;
	int count;
	ArcNode *firstarc;
}Vnode;
typedef struct
{
	Vnode adjlist[MAXV];
	int n,e;
}AdjGraph;

void CreateMat(MatGraph &g,int A[MAXV][MAXV],int n,int e)
{
	int i,j;
	g.n=n;g.e=e;
	for(i=0;i<g.n;i++)
	{
		for(j=0;j<g.n;j++)
		{
			g.edges[i][j]=A[i][j];
		}
	}
}

void DispMat(MatGraph g)
{
	int i,j;
	for(i=0;i<g.n;i++)
	{
		for(j=0;j<g.n;j++)
		{
			if(g.edges[i][j]!=INF)
			    cout<<" "<<g.edges[i][j]<<" ";
            else
                cout<<" "<<"…";
		}
		cout<<endl;
	}
}

void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e)
{
	int i,j;
	ArcNode *p;
	G=(AdjGraph*)malloc(sizeof(AdjGraph));
	for(i=0;i<n;i++)
	    G->adjlist[i].firstarc=NULL;
    for(i=0;i<n;i++)
        for(j=n-1;j>=0;j--)
            if(A[i][j]!=0&&A[i][j]!=INF)
            {
            	p=(ArcNode*)malloc(sizeof(ArcNode));
            	p->adjvex=j;
            	p->weight=A[i][j];
            	p->nextarc=G->adjlist[i].firstarc;
            	G->adjlist[i].firstarc=p;
            }
    G->n=n;G->e=n;
}
void DispAdj(AdjGraph *G)
{
	ArcNode *p;
	for(int i=0;i<G->n;i++)
	{
		p=G->adjlist[i].firstarc;
		cout<<i<<"：";
		while(p!=NULL)
		{
			cout<<p->adjvex<<"["<<p->weight<<"]->";
			p=p->nextarc;
		}
		cout<<"^"<<endl;
	}
}
void DestroyAdj(AdjGraph *&G)
{
	ArcNode *pre,*p;
	for(int i=0;i<G->n;i++)
	{
		pre=G->adjlist[i].firstarc;
		if(pre!=NULL)
		{
			p=pre->nextarc;
			while(p!=NULL)
			{
				free(pre);
				pre=p;p-p->nextarc;
			}
			free(pre);
		}
	}
	free(G);
}


int main()
{
	MatGraph g;
	AdjGraph *G;
	int A[MAXV][MAXV]=
	{
		{0,5,INF,7,INF,INF},{INF,0,4,INF,INF,INF},{8,INF,0,INF,INF,9},
		{INF,INF,5,0,INF,6},{INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0}
	};
	int n=6,e=10;
	CreateMat(g,A,n,e);
	cout<<"邻接矩阵为："<<endl;
	DispMat(g);
	CreateAdj(G,A,n,e);
	cout<<"邻接表为："<<endl;
	DispAdj(G);
	DestroyAdj(G);
	return 0;
}

